package com.lw.leetcode.add.e;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 这道题我不懂，记录一下。。
 * 664. 奇怪的打印机
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/20 13:55
 */
public class StrangePrinter {

    public static void main(String[] args) {
        StrangePrinter test = new StrangePrinter();

        // 2
        String str = "aaabbb";

        // 2
//        String str = "aba";

        int i = test.strangePrinter(str);
        System.out.println(i);
    }

    public int strangePrinter(String s) {
        int length = s.length();
        int[][] arr = new int[length][length];
        char[] chars = s.toCharArray();
        for (int i = length - 1; i >= 0; i--) {
            arr[i][i] = 1;
            for (int j = i + 1; j < length; j++) {
                if (chars[i] == chars[j]) {
                    arr[i][j] = arr[i + 1][j];
                } else {
                    int min = arr[i + 1][j] + 1;
                    for (int k = i + 1; k < j; k++) {
                        min = Math.min(min, arr[i][k] + arr[k + 1][j]);
                    }
                    arr[i][j] = min;
                }
            }
        }
        return arr[0][length - 1];
    }

}